package leetcode

// https://leetcode.com/problems/split-array-largest-sum/
func splitArray(nums []int, m int) int {
	total, max := 0, -1
	for _, v := range nums {
		total += v
		if v > max {
			max = v
		}
	}
	left, right := max, total

	for mid := left + (right-left)/2; left <= right; mid = left + (right-left)/2 {
		if check(nums, m, mid) {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

// check nums whether could split m continous subarrays, and max value is max_sum.
func check(nums []int, m, maxSum int) bool {
	prem, count := 0, 0
	for _, v := range nums {
		if count+v <= maxSum {
			count += v
		} else {
			count = v
			prem++
		}
	}
	return prem+1 <= m
}
